package it.storm.solution;

/**
 * 41. 缺失的第一个正数
 * https://leetcode-cn.com/problems/first-missing-positive/
 */
public class Solutions_41 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 0};  // output: 3
        int[] nums = {3, 4, -1, 1};  // output: 2   change：{1, 4, 3, 4}
//        int[] nums = {7, 8, 9, 11, 12};  // output: 1
//        int[] nums = {1};  // output: 2
//        int[] nums = {};  // output: 1

        int result = firstMissingPositive(nums);
        System.out.println(result);
    }

    /**
     * 原地算法完成
     */
    public static int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] > len) {
                // 把没有买票的，所以没有座位的人标记出来
                nums[i] = 0;
            }
        }

        for (int i = 0; i < len; i++) {
            // 判断 nums[i] 人员是否买了票，即大于 0 的元素，小于等于 0 的元素都是“非法上车”的
            if (nums[i] > 0) {
                // 判断 loca 元素是否坐在正确的座位上，例如：3 应该坐在索引 2 上
                int user = nums[i];

                // 若没有坐在对应的座位上时，进行“座位的调整”
                while (user != nums[user - 1]) {
                    // 记录下谁占用了自己的座位（若占用自己座位的人也买了票，那么这个人也要去找到自己的座位，不能被丢失了）
                    int temp = nums[user - 1];

                    // 自己坐回属于自己的座位上
                    nums[user - 1] = user;

                    if (temp < 1) {
                        // 占用自己座位的人 “没有买票”，就没有座位了，老老实实下车吧
                        break;
                    } else {
                        // 占用自己座位的人 也是“买了票的人",却没有坐对自己的位置上，
                        // 继续迭代寻找正确的座位，把占用了自己座位的人“赶走”
                        user = temp;
                    }
                }
            }
        }
        int i = 0;
        for (; i < len; i++) {
            if (nums[i] != i + 1) {
                // 例如：{1, 2, 4, 4}，第 1 个 4 与索引 i + 1 不同，即是 3 缺失了
                return i + 1;
            }
        }
        // 数组长度为 0 时，缺失的第一个最小正整数就是 1
        return i + 1;
    }
}
